Room 834
				Laboratory for Computer Science
				(formerly Project MAC)
				545 Technology Square
				Cambridge, Massachusetts 02139

				February 4, 1976

John Allen
Hewlett-Packard Research Lab
3500 Deer Creek Road
Palo Alto, California  94304

Dear John:

	Enclosed are the first two chapters of the book (The Anatomy of
LISP) with profuse corrections and comments.  The overall layout of the
book looks okay, but there are serious problems in Chapter Two that need
to be worked out.
	The most severe problem is the confusion about the "undefined"
object.  The use of "|λ←" to represent "undefined" comes, I believe, from
lattice theory, where the lattice ordering is on "amount of information".
The symbol "|λ←" (which I discovered is indeed called "bottom" in lattice
theory after I proofread page 15) is the lattice element weaker than any
other, and so represents "no information", while "T" ("top") represents
"too much information", i.e. an error or contradiction.
Thus "|λ←" is used to represent divergence, while "T" is used to represent
error situations such as car[FOO].  The two forms of undefinedness are
quite distinct and should not be confused.  Furthermore, your use of
several kinds of "|λ←" (or, more correctly, of "T") only leads to more
confusion; for example, you are forced to say that [FOO → BAR; t → BAZ]
is "undefined" rather than |λ←(Tr) or |λ←(S) on p. 22, footnote 13.
You would be much better off using a single, universal "|λ←" and "T"
rather than separate ones for each domain; in lattice-theoretic terms,
your combined domain of discourse would be the "coalesced sum"
of the disjoint lattices, which means the bottom and top elements
of each lattice (Tr, S, etc.) are identified.  This has support
in standard lattice-theoretic approaches to programming semantics
(see, for example, Stoy's Project MAC report on Scott-Strachey semantics).
	A second confusion is the assertion that CBN can somehow
subvert the requirement that a function be strict.  First, realize that if
we distinguish undefinedness from divergence, we can distinguish two
types of strictness: undefined-strict and diverging-strict.  Now, a function
can be declared strict in two ways.  One is to let the property of strictness
follow from the given definition; in this case a function may be
strict under one order of evaluation and not under another.
The other is to impose strictness as an auxiliary requirement.
In this case, in order to preserve the strictness property
it is necessary for every argument to be referenced to determine
whether it is undefined (or diverges); each argument must be referenced
if only for this purpose if you want the function to be strict.
Now suppose that you only look at the function's body to determine
strictness, and impose no auxiliary requirements.  Then CBN versus CBV
cannot possibly affect the issue of undefined-strictness, but only
of diverging-strictness.  For example:
	foo[x; y] <= [t → x; y]
is not undefined-strict under either CBN or CBV; it is diverging-
strict under CBV, but not under CBN.  The general statements one
can make are:
[1] a function diverging-strict under CBN is also diverging-strict
    under CBV.
[2] a function undefined-strict under any evaluation order is
    diverging-strict under that same order.
[3] a function diverging-strict under any evaluation order is
    undefined-strict if the body contains no non-undefined-strict
    functions other than the conditional expression.
	A third grievance is the use of M-expressions.
While they are of marginal help in a formal treatment of the
semantics of LISP, they are of no use whatsoever to the practical
LISP programmer, are confusing to the novice, and are for that matter
very difficult to read.  Similarly, the use of a separate domain Tr
is a great formal tool, but confusing to the aspiring LISP novice.
At many times during the course of the chapter I was uncertain as
to whether your intended audience was the LISP novices or the LISP
cognoscenti.  There are places that even I, a great LISP veteran,
had great difficulty understanding, whereas other places would
seem patronizing even to a beginning student.
Also, there is uncertainty in my mind whether you are writing
a treatise on LISP or on "structured programming".  If you want
to talk about structured programming in LISP, all well and good,
but you probably should assume the reader already knows LISP.
If you want to discuss LISP on a formal basis, distinguishing
various domains such as S and Tr, again you should assume the
reader knows LISP.  If you want to talk about LISP itself as a
programming language and system, then beginning formally is not the
best way to go.  (Most everyone agrees that LISP1.5M really lost
in that respect.  I spent three months understanding the first chapter,
and three days understanding the rest.)
	All this seems to be related to two basic misunderstandings
of LISP.  First of all, your mental model of LISP, as seen so far,
seems to be of good old LISP 1.5.  Great advances in LISP as a system have
been made since then (notably InterLISP and MacLISP).  Furthermore,
you seem to view LISP as a high-level language.  While this is true
in many respects, it is more properly viewed as "the machine language
of AI"!  Consider that LISP shares the following important characteristics
with machine language not possessed by most high-level languages:
	[1] Programs can trivially be treated as data.
	[2] In general, all data structures can be operated on
	    by the same set of primitive operators regardless
	    of type (an exception is numbers, but MacLISP supports
	    treating the bits of a flonum as a fixnum and vice versa!).
	    Thus CAR and RPLACA are literally to LISP as HLRZ and
	    HRLM are to the PDP-10: they can be used on any data object.
If you like, you may think of LISP as providing trivial implicit
coercions between domains:
	programs --> data (trivial)
	data --> programs (trivial)
	sexprs --> truth values (NIL=false, other=true)
	truth values --> sexprs (T and NIL)
What LISP provides is a general and powerful machine language for
implementing other data structures.  The power of CAR and CDR
may well be likened to the power of GOTO:  well used, it is a
powerful and invaluable tool; in particular, it is good for
compiling high-level constructs in terms of.  Abused, it leads
to unreadable programs.  I think these points deserve great stress
early in the game.
	Aside from these major points, there are a large number
of minor points that are largely detailed in the manuscript
itself in red.  One point is that when introducing identifiers
such as IND, PRF, or CBN, you should consistently say
immediately what the acronyms and abbreviations mean and why;
otherwise you are using an identifier only insiders will understand,
and from the novice's point of view you might as well have
called it ZBX or QGS.  Also, I would caution you against cuteness.
Besides the fact that cuteness is no substitute for humor,
and so obnoxious to the person who already knows the point being made,
it is unhelpful to the person who does not already understand the point.
This is just another case, really, of having to consider carefully
what is your intended audience.
	Now I admit that my comments may have been overly harsh,
particularly since I have not read the rest of the book yet.
It may be that many of the more philosophical problems are fixed
up later in the book; if so, I will extend my apologies when and
if I run across such patches.  I rather suspect, in fact, that given
your style of writing the implementation chapters will be far better
than the formal semantics chapters.  In the interests of getting
proofread material back to you quickly, however, I am forced
to judge chapters singly as I read them (and as a student would
have to read them), and so the above are my first impressions
of Chapter Two by itself.  I hope that my comments will prove
to be of use to you, and in fact my recommendation would be
a careful re-thinking and re-writing of the chapter.  I will send
you the other chapters, one by one, as I manage to read them.

				Yours,


				Guy L. Steele Jr.
				GLS @ MIT-AI
				 or @ MIT-ML

ββ